import javax.swing.tree.TreeNode;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86131
 * Date: 2024-01-26
 * Time: 15:39
 */
public class BinarySearchTree {
    static class TreeNode {  //内部类
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {  //构造方法
            this.val = val;
        }
    }

    public TreeNode root;

    //查找
    public boolean search(int val) {
        TreeNode cur = root;

        //创建一个cur在root位置,如果比cur大就走到右边,反之左边,直到cur等于空跳出循环

        while (cur != null) {
            if (cur.val < val) {
                //往右树查找
                cur = cur.right;
            } else if (cur.val > val) {
                //往左树查找
                cur = cur.left;
            } else {
                //找到了
                return true;
            }
        }
        //没有则返回false
        return false;
    }

    //插入
    //要记录上一个的结点
    public void insert(int val) {
        if (root == null) {  //第一个结点的处理
            root = new TreeNode(val);
            return;
        }
        TreeNode cur = root;
        TreeNode parent = null;

        while (cur != null) {  //cur走到空的地方,证明走到了,然后通过cur的父节点parent来判断插入左边还是右边
            if (cur.val < val) {
                parent = cur;  //先走到cur位置,cur再动
                cur = cur.right;
            } else if (cur.val > val) {
                parent = cur;
                cur = cur.left;
            } else {
                return;
            }
        }
        //new一个要插入的结点,把val放进去构造好
        TreeNode node = new TreeNode(val);
        //插入必须是叶子结点,所以cur到达null
        if (parent.val < val) {
            parent.right = node;
        } else {
            parent.left = node;
        }
    }

    //删除操作
    public void remove(int val) {
        TreeNode cur = root;  //从根节点开始找
        TreeNode parent = null;
        while(cur != null) {
            if(cur.val < val) {  //说明要删除的结点在cur的右边
                parent = cur;  //parent走到cur当前位置
                cur = cur.right;  //cur往右边走
            }else if(cur.val > val) {  ////说明要删除的结点在cur的左边
                parent = cur;  //parent走到cur当前位置
                cur = cur.left;  //cur往左边走
            }else {  //找到要删除的结点
                removeNode(parent,cur);
                return;
            }
        }
    }
    private void removeNode(TreeNode parent,TreeNode cur){
        if(cur.left == null) {  //左边等于空
            if (cur == null) {
                root = cur.right;
            } else if (cur == parent.left) {
                parent.left = cur.right;
            } else {
                parent.right = cur.right;
            }
        } else if (cur.right == null) {  //右边等于空
            if(cur == null) {
                root = cur.left;
            } else if (cur == parent.left) {
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }
        }else { //左右都不为空
            TreeNode t = cur.right;  //寻找所要删除结点右子树的最小值
            TreeNode tp = cur;
            while(t.left != null) {  //等于null说明找到最小值了
                tp = t;  //父亲结点先走到cur位置
                t = t.left;  //往左边寻找最小值
            }
            cur.val = t.val;  //进行替换
            if (tp.left == t.left) {  //删除结点,两种情况
                tp.left = t.right;
            } else {
                tp.right = t.right;
            }
        }
    }
}
